부산대학교자료구조
Scientific Inference Lab

First In, First Out

Queue ADT

큐(queue)는 뒤쪽(rear)에 넣고 앞쪽(front)에서 꺼내 먼저 넣은 값을 먼저 꺼내는 FIFO ADT다. 원형 큐는 배열의 앞 원소를 옮기지 않고 (j + i) mod m으로 위치를 계산해 두 연산을 O(1)로 만든다.

enqueue와 dequeueenqueue(x)는 뒤쪽에 추가하고 dequeue()는 앞쪽 값을 꺼낸다.
list의 한계pop(0)은 n − 1개를 옮겨 O(n)이다.
원형 큐배열 a, 앞쪽 인덱스 j, 원소 수 n으로 i번째 값을 (j + i) mod m에 둔다.

큐는 먼저 넣은 값을 먼저 꺼낸다

단계를 옮기면 연산 하나가 실행되고 앞쪽 값, 뒤쪽 값, 꺼낸 값, 원소 수가 바뀐다.

    위 줄은 큐이며 왼쪽이 앞쪽, 오른쪽이 뒤쪽이다. 초록 테두리 칸은 방금 넣은 값이다. 아래는 연산 순서이고 짙은 줄이 방금 실행한 연산이다.

    원형 큐는 앞쪽 인덱스와 원소 수로 논리 순서를 배열에 감는다

    앞쪽 인덱스 j와 원소 수 n을 바꾸면 A, B, C, …가 놓이는 배열 인덱스, 다음 enqueue 위치, 빈 상태와 가득 찬 상태가 바뀐다. 배열 길이는 m = 8이다.

    칸 위 숫자는 배열 인덱스다. 파란 칸은 큐에 든 값이고 초록 테두리 칸은 앞쪽 j, 점선 칸은 빈 칸이다.